package com.zjj.algorithm.learning.leetcode.array;

/**
 * 4. 寻找两个正序数组的中位数   困难题
 * <p>
 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
 * <p>
 * 算法的时间复杂度应该为 O(log (m+n)) 。
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums1 = [1,3], nums2 = [2]
 * 输出：2.00000
 * 解释：合并数组 = [1,2,3] ，中位数 2
 * 示例 2：
 * <p>
 * 输入：nums1 = [1,2], nums2 = [3,4]
 * 输出：2.50000
 * 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
 *
 * @author zjj_admin
 * @date 2022/11/24 17:18
 */
public class MedianOfTwoSortedArrays {

    public static void main(String[] args) {

        int[] nums1 = new int[]{1, 2};
        int[] nums2 = new int[]{3, 4};
        double res = findMedianSortedArrays(nums1, nums2);
        System.out.println("res = " + res);

    }

    /**
     * 时间
     * 1 ms
     * 击败
     * 100%
     * 内存
     * 42.4 MB
     * 击败
     * 41.68%
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int index1;
        int index2 = 0;
        int len = nums1.length + nums2.length;
        if (len % 2 == 0) {
            index1 = (len / 2);
            index2 = index1 + 1;
        } else {
            index1 = (len / 2) + 1;
        }
        int l1 = 0;
        int l2 = 0;
        int index = 0;

        int num1 = 0;
        int num2;
        double res;
        boolean isNums1 = true;
        while (true) {
            if (index == index1) {
                int j1 = l1 - 1;
                int j2 = l2 - 1;
                if (len % 2 == 0) {
                    num1 = isNums1 ? nums1[j1] : nums2[j2];
                } else {
                    res = isNums1 ? nums1[j1] : nums2[j2];
                    return res;
                }
            }
            if (index != 0 && index == index2) {
                int j1 = l1 - 1;
                int j2 = l2 - 1;
                num2 = isNums1 ? nums1[j1] : nums2[j2];
                return (float) (num1 + num2) / 2;
            }

            //******************************
            if (l1 < nums1.length && l2 < nums2.length) {
                if (nums1[l1] <= nums2[l2]) {
                    l1++;
                    isNums1 = true;
                } else {
                    l2++;
                    isNums1 = false;
                }
            } else if (l1 == nums1.length && l2 < nums2.length) {
                l2++;
                isNums1 = false;
            } else if (l1 < nums1.length && l2 == nums2.length) {
                l1++;
                isNums1 = true;
            }
            index++;
        }

    }


}
